﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
using System.Collections;

namespace BinaryTree
{
         public class TTreeNode
        {
            public string name;
            public TTreeNode left, right;

            // Constructor  to create a single node 
            public TTreeNode(string name)
            {
                this.name = name;
                left = null;
                right = null;
            }
        }


        // The Binary tree itself
        public class TBinarySTree
        {
            // Implements:

            // count()
            // clear()
            // insert()
            // delete()
            // findSymbol()
            //
            // Usage:
            //
            //  TBinarySTree bt = new TBinarySTree();
            //  bt.insert ("Bill", "3.14");
            //  bt.insert ("John". 2.71");
            //  etc.
            //  node = bt.findSymbol ("Bill");
            //  WriteLine ("Node value = {0}\n", node.value);
            //

            private TTreeNode root;     // Points to the root of the tree
            private int _count = 0;

            public TBinarySTree()
            {
                root = null;
                _count = 0;
            }


            // Recursive destruction of binary search tree, called by method clear
            // and destroy. Can be used to kill a sub-tree of a larger tree.
            // This is a hanger on from its Delphi origins, it might be dispensable
            // given the garbage collection abilities of .NET
            private void killTree(ref TTreeNode p)
            {
                if (p != null)
                {
                    killTree(ref p.left);
                    killTree(ref p.right);
                    p = null;
                }
            }

            /// <summary>
            /// Clear the binary tree.
            /// </summary>
            public void clear()
            {
                killTree(ref root);
                _count = 0;
            }

            /// <summary>
            /// Returns the number of nodes in the tree
            /// </summary>
            /// <returns>Number of nodes in the tree</returns>
            public int count()
            {
                return _count;
            }

            /// <summary>
            /// Find name in tree. Return a reference to the node
            /// if symbol found else return null to indicate failure.
            /// </summary>
            /// <param name="name">Name of node to locate</param>
            /// <returns>Returns null if it fails to find the node, else returns reference to node</returns>
            /// 

            public ArrayList wereSearched = new ArrayList();
            public struct inds
            {
                public int indLeft, indRight;

                public inds(int p1, int p2)
                {
                    indLeft = p1;
                    indRight = p2;
                }
            }

            public TTreeNode findSymbol(string name)
            {
                createIndexList();
                wereSearched.Clear();
                TTreeNode np = root;
                int cmp;
                int newInd = 0;
                while (np != null)
                {

                    int idName, idNpName;

                    if ((int.TryParse(name, out idName)) && (int.TryParse(np.name, out idNpName)))
                    {
                        wereSearched.Add(newInd);
                        if (idName == idNpName)
                        {
                            return np;
                        }
                        if (idName < idNpName)
                        {
                            newInd = ((inds)aList[newInd]).indLeft;
                            np = np.left;
                        }
                        else
                        {
                            newInd = ((inds)aList[newInd]).indRight;
                            np = np.right;
                        }

                    }
                    else
                    {

                        cmp = String.Compare(name, np.name);

                        wereSearched.Add(newInd);

                        if (cmp == 0)   // found !
                            return np;


                        if (cmp < 0)
                        {

                            newInd = ((inds)aList[newInd]).indLeft;
                            np = np.left;

                        }
                        else
                        {
                            newInd = ((inds)aList[newInd]).indRight;
                            np = np.right;
                        }
                    }
                }
                return null;  // Return null to indicate failure to find name
            }


            // Recursively locates an empty slot in the binary tree and inserts the node
            private void add(TTreeNode node, ref TTreeNode tree)
            {
                if (tree == null)
                    tree = node;
                else
                {
                    // If we find a node with the same name then it's 
                    // a duplicate and we can't continue
                    int idNode, idTree;

                    if ((int.TryParse(node.name, out idNode)) && (int.TryParse(node.name, out idTree)))
                    {
                        if (idNode == idTree)
                        {
                            throw new Exception();
                        }
                        if (Math.Min(idNode, idTree) == idNode)
                        {
                            add(node, ref tree.left);
                        }
                        else
                        {
                            add(node, ref tree.right);
                        }

                    }
                    else
                    {
                        int comparison = String.CompareOrdinal(node.name, tree.name);
                        if (comparison == 0)
                            throw new Exception();

                        if (comparison < 0)
                        {
                            add(node, ref tree.left);
                        }
                        else
                        {
                            add(node, ref tree.right);
                        }
                    }
                }
            }
            public ArrayList aList = new ArrayList();
            public void createIndexList()
            {


                inds ind0 = new inds(1, 2);
                aList.Add(ind0);
                inds ind1 = new inds(3, 4);
                aList.Add(ind1);
                inds ind2 = new inds(5, 6);
                aList.Add(ind2);
                inds ind3 = new inds(7, 8);
                aList.Add(ind3);
                inds ind4 = new inds(9, 10);
                aList.Add(ind4);
                inds ind5 = new inds(11, 12);
                aList.Add(ind5);
                inds ind6 = new inds(13, 14);
                aList.Add(ind6);
                inds indNull = new inds(0, 0);
                aList.Add(indNull);
                aList.Add(indNull);
                aList.Add(indNull);
                aList.Add(indNull);
                aList.Add(indNull);
                aList.Add(indNull);
                aList.Add(indNull);
                aList.Add(indNull);
            }

            public int altura(TTreeNode r)
            {
                if (r == null)
                    return -1; // altura de árvore vazia é -1
                else
                {
                    int he = altura(r.left);
                    int hd = altura(r.right);
                    if (he < hd) return hd + 1;
                    else return he + 1;
                }
            }

            public bool nodoJaInserido = false;
            private void addToHeight(TTreeNode node, ref TTreeNode tree, int height)
            {
                if (tree == null)
                    tree = node;
                else
                {
                    // If we find a node with the same name then it's 
                    // a duplicate and we can't continue

                    int idNode, idTree;

                    if ((int.TryParse(node.name, out idNode)) && (int.TryParse(tree.name, out idTree)))
                    {
                        if (idNode == idTree)
                        {
                            MessageBox.Show("O nodo já foi inserido");
                            nodoJaInserido = true;
                            return;
                        }
                        if (Math.Min(idNode, idTree) == idNode)
                        {
                            addToHeight(node, ref tree.left, height);
                            if (!(altura(root) < height))
                            {
                                this.delete(node.name);
                                throw new Exception();
                            }
                        }
                        else
                        {
                            addToHeight(node, ref tree.right, height);
                            if (!(altura(root) < height))
                            {
                                this.delete(node.name);
                                throw new Exception();
                            }
                        }

                    }
                    else
                    {

                        int comparison = String.Compare(node.name, tree.name);
                        if (comparison == 0)
                        {
                            MessageBox.Show("O nodo já foi inserido");
                            nodoJaInserido = true;
                            //throw new Exception();
                            return;
                        }

                        if (comparison < 0)
                        {
                            addToHeight(node, ref tree.left, height);
                            if (!(altura(root) < height))
                            {
                                this.delete(node.name);
                                throw new Exception();
                            }

                        }
                        else
                        {
                            // heightRight++;
                            addToHeight(node, ref tree.right, height);
                            if (!(altura(root) < height))
                            {
                                this.delete(node.name);
                                throw new Exception();
                            }

                        }
                    }
                }
            }
            /// <summary>
            /// Add a symbol to the tree if it's a new one. Returns reference to the new
            /// node if a new node inserted, else returns null to indicate node already present.
            /// </summary>
            /// <param name="name">Name of node to add to tree</param>
            /// <param name="d">Value of node</param>
            /// <returns> Returns reference to the new node is the node was inserted.
            /// If a duplicate node (same name was located then returns null</returns>
            public TTreeNode insert(string name)
            {
                TTreeNode node = new TTreeNode(name);
                try
                {
                    if (root == null)
                        root = node;
                    else
                        add(node, ref root);
                    _count++;
                    return node;
                }
                catch (Exception)
                {
                    return null;
                }
            }

            public TTreeNode insertToHeight(string name, int height)
            {
                TTreeNode node = new TTreeNode(name);

                nodoJaInserido = false;
                try
                {
                    if (root == null)
                        root = node;
                    else
                        addToHeight(node, ref root, height);
                    _count++;
                    return node;
                }
                catch (Exception)
                {
                    return null;

                }
            }

            // Searches for a node with name key, name. If found it returns a reference
            // to the node and to thenodes parent. Else returns null.
            private TTreeNode findParent(string name, ref TTreeNode parent)
            {
                TTreeNode np = root;
                parent = null;
                int cmp;
                while (np != null)
                {
                    cmp = String.Compare(name, np.name);
                    if (cmp == 0)   // found !
                        return np;

                    if (cmp < 0)
                    {
                        parent = np;
                        np = np.left;
                    }
                    else
                    {
                        parent = np;
                        np = np.right;
                    }
                }
                return null;  // Return null to indicate failure to find name
            }

            /// <summary>
            /// Find the next ordinal node starting at node startNode.
            /// Due to the structure of a binary search tree, the
            /// successor node is simply the left most node on the right branch.
            /// </summary>
            /// <param name="startNode">Name key to use for searching</param>
            /// <param name="parent">Returns the parent node if search successful</param>
            /// <returns>Returns a reference to the node if successful, else null</returns>
            public TTreeNode findSuccessor(TTreeNode startNode, ref TTreeNode parent)
            {
                parent = startNode;
                // Look for the left-most node on the right side
                startNode = startNode.right;
                while (startNode.left != null)
                {
                    parent = startNode;
                    startNode = startNode.left;
                }
                return startNode;
            }

            public TTreeNode findPred(TTreeNode startNode, ref TTreeNode parent)
            {
                parent = startNode;
                // Look for the right-most node on the left side
                startNode = startNode.left;
                while (startNode.right != null)
                {
                    parent = startNode;
                    startNode = startNode.right;
                }
                return startNode;
            }

            /// <summary>
            /// Delete a given node. This is the more complex method in the binary search
            /// class. The method considers three senarios, 1) the deleted node has no
            /// children; 2) the deleted node as one child; 3) the deleted node has two
            /// children. Case one and two are relatively simple to handle, the only
            /// unusual considerations are when the node is the root node. Case 3) is
            /// much more complicated. It requires the location of the successor node.
            /// The node to be deleted is then replaced by the successor node and the
            /// successor node itself deleted. Throws an exception if the method fails
            /// to locate the node for deletion.
            /// </summary>
            /// <param name="key">Name key of node to delete</param>
            public void delete(string key)
            {
                TTreeNode parent = null;
                // First find the node to delete and its parent
                TTreeNode nodeToDelete = findParent(key, ref parent);
                if (nodeToDelete == null)
                {
                    // throw new Exception("Unable to delete node: " + key.ToString());  // can't find node, then say so 
                    // MessageBox.Show("Nodo não encontrado");
                    return;

                }

                // Three cases to consider, leaf, one child, two children

                // If it is a simple leaf then just null what the parent is pointing to
                if ((nodeToDelete.left == null) && (nodeToDelete.right == null))
                {
                    if (parent == null)
                    {
                        root = null;
                        return;
                    }

                    // find out whether left or right is associated 
                    // with the parent and null as appropriate
                    if (parent.left == nodeToDelete)
                        parent.left = null;
                    else
                        parent.right = null;
                    _count--;
                    return;
                }

                // One of the children is null, in this case
                // delete the node and move child up
                if (nodeToDelete.left == null)
                {
                    // Special case if we're at the root
                    if (parent == null)
                    {
                        root = nodeToDelete.right;
                        return;
                    }

                    // Identify the child and point the parent at the child
                    if (parent.left == nodeToDelete)
                        parent.left = nodeToDelete.right;
                    else
                        parent.right = nodeToDelete.right;
                    nodeToDelete = null; // Clean up the deleted node
                    _count--;
                    return;
                }

                // One of the children is null, in this case
                // delete the node and move child up
                if (nodeToDelete.right == null)
                {
                    // Special case if we're at the root			
                    if (parent == null)
                    {
                        root = nodeToDelete.left;
                        return;
                    }

                    // Identify the child and point the parent at the child
                    if (parent.left == nodeToDelete)
                        parent.left = nodeToDelete.left;
                    else
                        parent.right = nodeToDelete.left;
                    nodeToDelete = null; // Clean up the deleted node
                    _count--;
                    return;
                }

                // Both children have nodes, therefore find the successor, 
                // replace deleted node with successor and remove successor
                // The parent argument becomes the parent of the successor
                TTreeNode successor = findSuccessor(nodeToDelete, ref parent);
                // Make a copy of the successor node
                TTreeNode tmp = new TTreeNode(successor.name);
                // Find out which side the successor parent is pointing to the
                // successor and remove the successor
                if (parent.left == successor)
                    parent.left = successor.right;
                else
                    parent.right = successor.right;

                // Copy over the successor values to the deleted node position
                nodeToDelete.name = tmp.name;

                _count--;
            }





            public void deletePred(string key)
            {
                TTreeNode parent = null;
                // First find the node to delete and its parent
                TTreeNode nodeToDelete = findParent(key, ref parent);
                if (nodeToDelete == null)
                {
                    // throw new Exception("Unable to delete node: " + key.ToString());  // can't find node, then say so 
                    MessageBox.Show("Nodo não encontrado");
                    return;

                }

                // Three cases to consider, leaf, one child, two children

                // If it is a simple leaf then just null what the parent is pointing to
                if ((nodeToDelete.left == null) && (nodeToDelete.right == null))
                {
                    if (parent == null)
                    {
                        root = null;
                        return;
                    }

                    // find out whether left or right is associated 
                    // with the parent and null as appropriate
                    if (parent.left == nodeToDelete)
                        parent.left = null;
                    else
                        parent.right = null;
                    _count--;
                    return;
                }

                // One of the children is null, in this case
                // delete the node and move child up
                if (nodeToDelete.left == null)
                {
                    // Special case if we're at the root
                    if (parent == null)
                    {
                        root = nodeToDelete.right;
                        return;
                    }

                    // Identify the child and point the parent at the child
                    if (parent.left == nodeToDelete)
                        parent.left = nodeToDelete.right;
                    else
                        parent.right = nodeToDelete.right;
                    nodeToDelete = null; // Clean up the deleted node
                    _count--;
                    return;
                }

                // One of the children is null, in this case
                // delete the node and move child up
                if (nodeToDelete.right == null)
                {
                    // Special case if we're at the root			
                    if (parent == null)
                    {
                        root = nodeToDelete.left;
                        return;
                    }

                    // Identify the child and point the parent at the child
                    if (parent.left == nodeToDelete)
                        parent.left = nodeToDelete.left;
                    else
                        parent.right = nodeToDelete.left;
                    nodeToDelete = null; // Clean up the deleted node
                    _count--;
                    return;
                }

                // Both children have nodes, therefore find the successor, 
                // replace deleted node with successor and remove successor
                // The parent argument becomes the parent of the successor
                TTreeNode pred = findPred(nodeToDelete, ref parent);
                // Make a copy of the successor node
                TTreeNode tmp = new TTreeNode(pred.name);
                // Find out which side the successor parent is pointing to the
                // successor and remove the successor
                if (parent.right == pred)
                    parent.right = pred.left;
                else
                    parent.left = pred.left;

                // Copy over the successor values to the deleted node position
                nodeToDelete.name = tmp.name;

                _count--;
            }



















            // Simple 'drawing' routines
            private string drawNode(TTreeNode node)
            {
                if (node == null)
                    return "empty";

                if ((node.left == null) && (node.right == null))
                    return node.name;
                if ((node.left != null) && (node.right == null))
                    return node.name + "(" + drawNode(node.left) + ", _)";

                if ((node.right != null) && (node.left == null))
                    return node.name + "(_, " + drawNode(node.right) + ")";

                return node.name + "(" + drawNode(node.left) + ", " + drawNode(node.right) + ")";
            }


            /// <summary>
            /// Return the tree depicted as a simple string, useful for debugging, eg
            /// 50(40(30(20, 35), 45(44, 46)), 60)
            /// </summary>
            /// <returns>Returns the tree</returns>
            public string drawTree()
            {
                return drawNode(root);
            }

            public TTreeNode getRoot()
            {
                return root;
            }

        }
 

}
